# -*- coding: utf-8 -*-

"""剑指 Offer II 043. 往完全二叉树添加节点
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的根节点。

示例 1：
输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：
输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

提示：
最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
每个测试用例最多调用 CBTInserter.insert  操作 10000 次。
给定节点或插入节点的每个值都在 0 到 5000 之间。"""


from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class CBTInserter:
    """重在插入，借鉴完全二叉树的数组表示方法，在数组表示中，完全二叉树占满数组的每个位置，父子节点存在 child//parent == 2 的关系
    
    可是本题为引用节点，但是只有插入功能，借鉴数组方案的数学关系，可以维持一个节点数，来计算待插入的父节点。

    在继续读题的过程中，发现一开始初始化时就已经给了一个二叉树，以引用关系建立的，所以需要找到最近的可以挂载子节点的父节点，完全二叉树的结构，需要层遍历。
    如何处理层遍历呢？首先想到的是维护一个队列（先进先出），每次从队列中取出需要访问的节点，并在访问节点过程中，将新子节点添加到队列中；
    此时在做第一次 insert 调用之前，需要先初始化任务队列，倒不如直接在初始化过程中完成该队列的初始化。
    值得鼓励的是，在此之前只见过层遍历的习题，并没有研究过，此时想到用队列也是建立在对前面课程与习题的消化的基础上才能想到。"""

    def __init__(self, root: TreeNode):
        self.root = root
        self.wait_child_nodes = deque([root])
        while True:
            parent = self.wait_child_nodes.popleft()
            if parent.left:
                self.wait_child_nodes.append(parent.left)
            if parent.right:
                self.wait_child_nodes.append(parent.right)
            
            if not (parent.left and parent.right):
                self.wait_child_nodes.appendleft(parent)
                break

    def insert(self, v: int) -> int:
        child = TreeNode(val=v)
        self.wait_child_nodes.append(child)

        parent = self.wait_child_nodes.popleft()
        if not parent.left:
            parent.left = child
            self.wait_child_nodes.appendleft(parent)
        else:
            parent.right = child
        return parent.val

    def get_root(self) -> TreeNode:
        return self.root


if __name__ == '__main__':
# Your CBTInserter object will be instantiated and called as such:
    cbtInserter = CBTInserter([1,2,3,4,5,6])
    print(cbtInserter.insert(7))
    print(cbtInserter.insert(8))
    print(cbtInserter.get_root())
